\documentclass[11pt,letterpaper]{article}

\newcommand{\mytitle}{CS255 Homework 1}
\newcommand{\myauthor}{Kevin Lewi}
\date{February 1, 2012}

\usepackage{hwformat}

\begin{document}

\maketitle

\section*{Problem 0}

I would say that it's better to compress the data and then encrypt the result. 
Since the plaintext gets encrypted either way, security is not really the issue 
here --- rather, it seems like if you encrypt it first, the compression will not 
be as strong as if you were to compress first and then encrypt, since encryption 
causes the plaintext to look random, and random stuff is not very compressible.

\section*{Problem 1}

\subsection*{(a)}

Let $f$ be the encryption function using $K_{AB}$ and $g$ the encryption 
functinon using $K_{AC}$. Alice can first choose a key $K$ at random and xor it 
with the message $M$. Then, she can compute $g(f(K))$ and use this as the 
header. Thus, she sends the message

\[ g(f(K)) || K \oplus M \]

\subsection*{(b)}

Let $h$ be the encryption function using $K{AD}$. Again, Alice can choose a 
random $K$, and this time she can output the message

\[ f(g(K) || f(h(K)) || g(h(K)) || K \oplus M \]

Any two people will be able to get together and decrypt one of the three blocks 
in the header, which will then give them the key to recover the message.

\subsection*{(c)}

The size of the header is on the order of $\binom{n}{k}$, which is poor.

\section*{Problem 2}

\subsection*{(a)}

Only two blocks of the plaintext will be corrupted, the block associated with 
$\ell/2$ and the block after that.

\subsection*{(b)}

The only block corrupted in randomized counter mode will be block $\ell/2$, 
since no other blocks rely on it.

\section*{Problem 3}

\subsection*{(a)}

The adversary first sends a message $m_1$ --- let $x$ be the ciphertext, and 
$x_0$ be the last block of $x$. The adversary then sends $x_0$ as the message. 
Note that what he gets back as a ciphertext, call it $y$, will be the encryption 
of the all-zeroes string. This is because, when he sends $x_0$ as the message, 
$x_0$ is also the IV, so that they are xor'd together and encrypted as the the 
encryption of the all-zeroes string. Also, the IV for the next message will be 
$y$.

Now, the adversary sends two messages: $y$ and some string $z \neq y$. Now, the 
adversary performas as follows: if the challenge ciphertext is $y$, then he 
outputs that $y$ was also encrypted --- otherwise, he outputs that $z$ was 
encrypted.

Note that if $y$ was encrypted, then, since the IV is also $y$, the output will 
be the encryption of the all-zeroes string, which is still $y$. This happens 
with probability $1$. Thus, the probability that the encryption of $y \oplus z$ 
for $z \neq y$ is also equal to $y$ is negligible. Therefore, we can conclude 
that our advantage is $1$ with high probability.

\subsection*{(b)}

Maintain a second secret key $K_2$ (other than the first key already being used 
in the encryption scheme). Rather than using the last ciphertext block as the IV 
to the next packet, first encrypt the last ciphertext block under $K_2$ using 
AES, and use the output as the IV to the next packet.

\subsection*{(c)}

Let $x$ be the all-zeroes string, $y$ be the all-zeroes string except for a $1$ 
as the last bit, and $z$ some string that is neither $x$ nor $y$. First, send 
$x$ to be encrypted, and take note of the resulting IV and ciphertext. Call this 
IV $IV_x$.

Now, as the challenge, submit strings $y$ and $z$ to be encrypted. If the 
challenge ciphertext's IV is equal to $IV_x$ but with the last bit flipped, then 
the ciphertext will be identical to the ciphertext received when we encrypted 
$x$, and so we can output one in this case. In all other cases, we can simply 
guess randomly. Therefore, our advantage is $1/2^n$, since the probability that 
the trivial case happens is $1/2^n$ (since there are $2^n$ strings total).

\section*{Problem 4}

$F$ is not secure. The adversary can submit the following three messages $x = 
1000 \cdots$, $y = 01000 \cdots$, $z = 001000 \cdots$.

Thus, $F(k,x) = k[0] \oplus k[1]$, $F(k,y) = k[0] \oplus k[2]$, $F(k,z) = k[0] 
\oplus k[3]$, and so let $b = F(k,x) \oplus F(k,y) \oplus F(k,z) = k[0] \oplus 
k[1] \oplus k[2] \oplus k[3]$. Then, the adversary can send for the challenge 
the message $111000 \cdots$, and he will already know the output will be $b$.

\section*{Problem 5}

\subsection*{(a)}

Let $P$ be the path from the root of the tre to DVD $r$, and let $p_1, \cdots, 
p_j$ be the nodes on this path. For each $i$, note that $p_i$ is the parent of 
$p_{i+1}$. Let $S$ be the set of all nodes such that for $v \in S$, there exists 
some $i$ such that $p_i$ is the parent of $v$ and $p_{i+1} \neq v$. Note that 
$|S| \leq \log_2(n)$.

The set $S$ has the property that every player except for player $r$ has access 
to at least one key in $S$. Now, we can just encrypt the key $K$ once under each 
element $v \in S$, and use this as the header for the movie. Thus, every player 
other than $r$ will be able to recover the key from at least one of the 
$\log_2(n)$ encryptions in the header, except for player $r$ who cannot recover 
any of them.

\subsection*{(b)}

The concept is the exact same as part a. We can compute a set $S_i$ for each 
player $r_i$ that needs to have its access revoked, and then just take the union 
of these sets. This union will have size $O(k \log n)$, and we can use the same 
procedure to ensure that everyone has access except for those $k$ exposed 
players.

\section*{Problem 6}

\subsection*{(a)}

For all $i$, every player has access to either $k_{i,0}$ or $k_{i,1}$, and so 
will each player will be able to decrypt either the second or third member of 
the triple, which is enough to recover $m$.

\subsection*{(b)}

The content provider can first fix two distinct messages $m_0$ and $m_1$, and 
then, for each $i$, broadcast $(i, E(k_{i,0},m_0), E(k_{i,1},m_1))$ and observe 
which message $P$ is able to play. This will tell the content provider which bit 
$P$ has access to for each $i$, and if done for all $i$, reveals the bit 
encoding of $P$.

\subsection*{(c)}

Since $i \oplus j$ is not a power of $2$, there are at least two bit positions 
for which $i$ and $j$ differ. Let these positions be $p_1$ and $p_2$. Let $k$ be 
the bit encoding that is exactly equal to $i$, except that at $p_1$, $k$'s bit 
is flipped from $i$. Note that $k \neq j$.

The pirate can simply build a player $P$ that pretends it is $k$, which is 
possible since it has access to all of $k$'s bits. Then, it evades detection 
because the tracing algorithm will think that $k$ built the player $P$.



\end{document}
